package com.github.hgkmail.hello.leetcode101.firstsearch;

public class LC547NumberOfProvinces {
    //返回相连的城市数
    public int findConnectedCity(int[][] isConnected, int[] visited, int i) {
        if (i<0 || i>=isConnected.length || visited[i]==1) {
            return 0;
        }
        visited[i]=1;
        int cityNum=1;
        for (int j = 0; j < isConnected.length; j++) {
            if (i==j) {
                continue;
            }
            if (isConnected[i][j]==1 && visited[j]==0) {
                cityNum+=findConnectedCity(isConnected, visited, j);
            }
        }

        return cityNum;
    }

    public int findCircleNum(int[][] isConnected) {
        int[] visited=new int[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            visited[0]=0; //未访问过
        }
        int provinceNum=0;
        for (int i = 0; i < isConnected.length; i++) {
            if (findConnectedCity(isConnected, visited, i)>0) {
                provinceNum+=1;
            }
        }

        return provinceNum;
    }

    public static void main(String[] args) {
        System.out.println(new LC547NumberOfProvinces().findCircleNum(new int[][]{
                {1,1,0},{1,1,0},{0,0,1}
        }));
    }
}
